The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
separation systems provide a simple general framework in which both tree-shape and high cohesion of many combinatorial structures can be expressed, and their duality proved. Applications range from tangle-type duality and tree structure theorems in graphs, matroids or CW-complexes to, potentially, image segmentation and cluster analysis. This paper is intended as a concise common reference for the...
We pursue the idea of generalizing Hindman’s Theorem to uncountable cardinalities, by analogy with the way in which Ramsey’s Theorem can be generalized to weakly compact cardinals. But unlike Ramsey’s Theorem, the outcome of this paper is that the natural generalizations of Hindman’s Theorem proposed here tend to fail at all uncountable cardinals.
A finite lattice is interval dismantlable if it can be partitioned into an ideal and a filter, each of which can be partitioned into an ideal and a filter, etc., until you reach 1-element lattices. In this note, we find a quasi-equational basis for the pseudoquasivariety of interval dismantlable lattices, and show that there are infinitely many minimal interval non-dismantlable lattices.
One partially ordered set, Q, is a Tukey quotient of another, P, if there is a map ϕ : P → Q carrying cofinal sets of P to cofinal sets of Q. Two partial orders which are mutual Tukey quotients are said to be Tukey equivalent. Let X be a space and denote by K(X) $\mathcal {K}(X)$ the set of compact subsets of X, ordered by inclusion. The principal object of this paper is to analyze the Tukey equivalence...
We study an abstract notion of tree structure which lies at the common core of various tree-like discrete structures commonly used in combinatorics: trees in graphs, order trees, nested subsets of a set, tree-decompositions of graphs and matroids etc.Unlike graph-theoretical or order trees, these tree sets can provide a suitable formalization of tree structure also for infinite graphs, matroids, and...
A partial lattice P is ideal-projective, with respect to a class C of lattices, if for every K∈C and every homomorphism φ of partial lattices from P to the ideal lattice of K, there are arbitrarily large choice functions f:P→K for φ that are also homomorphisms of partial lattices. This extends the traditional concept of (sharp) transferability of a lattice with respect...
We show that atoms of the n-generated free left-handed skew Boolean intersection algebra are in a bijective correspondence with pointed partitions of non-empty subsets of {1,2,…,n} $\{1,2,\dots , n\}$. Furthermore, under the canonical inclusion into the k-generated free algebra, where k≥n, an atom of the n-generated free algebra decomposes into an orthogonal join of atoms of the k-generated free...
The symmetric group Sn acts naturally on the poset of injective words over the alphabet {1, 2,…,n}. The induced representation on the homology of this poset has been computed by Reiner and Webb. We generalize their result by computing the representation of Sn on the homology of all rank-selected subposets, in the sense of Stanley. A further generalization to the...
Motivated by applications to information retrieval, we study the lattice of antichains of finite intervals of a locally finite, totally ordered set. Intervals are ordered by reverse inclusion; the order between antichains is induced by the lower set they generate. We discuss in general properties of such antichain completions; in particular, their connection with Alexandrov completions. We prove the...
Generalizing the well known and exploited relation between Heyting and Nelson algebras to semi-Heyting algebras, we introduce the variety of semi-Nelson algebras. The main tool for its study is the construction given by Vakarelov. Using it, we characterize the lattice of congruences of a semi-Nelson algebra through some of its deductive systems, use this to find the subdirectly irreducible algebras,...
We consider two types of discrete-time Markov chains where the state space is a graded poset and the transitions are taken along the covering relations in the poset. The first type of Markov chain goes only in one direction, either up or down in the poset (an up chain or down chain). The second type toggles between two adjacent rank levels (an up-and-down chain). We introduce two compatibility concepts...
We develop an algorithm for efficiently computing recursively defined functions on posets. We illustrate this algorithm by disproving conjectures about the game Subset Takeaway (Chomp on a hypercube) and computing the number of linear extensions of the lattice of a 7-cube and related lattices.
Given a finite poset P, the intensively studied quantity La(n, P) denotes the largest size of a family of subsets of [n] not containing P as a weak subposet. Burcsi and Nagy (J. Graph Theory Appl. 1, 40–49 2013) proposed a double-chain method to get an upper bound La(n,P)≤12(|P|+h−2)n⌊n/2⌋ ${\mathrm La}(n,P)\le \frac {1}{2}(|P|+h-2)\left (\begin {array}{c}n \\ \lfloor {n/2}\rfloor \end {array}\right...
We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection graph have order dimension at most four. Starting from this observation we provide a comprehensive study of classes of graphs between grid intersection graphs and bipartite permutation graphs and the containment relation...
We present a probabilistic characterization of the dominance order on partitions. Let ν be a partition and Yν its Ferrers diagram, i.e. a stack of rows of cells with row i containing νi cells. Let the cells of Yν be filled with independent and identically distributed draws from the random variable X = Bin(r, p) with r ≥ 1 and p ∈ (0, 1). Given j, t ≥ 0, let P(ν, j, t) be the probability that the sum...
In this paper, we present a topological duality for a category of partially ordered sets that satisfy a distributivity condition studied by David and Erné. We call these posets mo-distributive. Our duality extends a duality given by David and Erné because our category of spaces has the same objects as theirs but the class of morphisms that we consider strictly includes their morphisms. As a consequence...
We give group analogs of two important theorems of real algebra concerning convex valuations, one of which is the Baer-Krull theorem. We do this by using quasi-orders, which gives a uniform approach to valued and ordered groups. We also recover the classical Baer-Krull theorem from its group analog.
We prove that finite partial orders with a linear extension form a Ramsey class. Our proof is based on the fact that the class of acyclic graphs has the Ramsey property and uses the partite construction.
Daligault, Rao and Thomassé asked whether a hereditary class of graphs well-quasi-ordered by the induced subgraph relation has bounded clique-width. Lozin, Razgon and Zamaraev recently showed that this is not true for classes defined by infinitely many forbidden induced subgraphs. However, in the case of finitely many forbidden induced subgraphs the question remains open and we conjecture that in...
We consider a lattice generated by three elements, two of which are semi-normal. We have proved it is infinite and have also found an additional condition for the lattice to be modular. As a result, it is proved that the sublattice generated in the subgroup lattice by two normal subgroups and any subgroup is modular.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.